#include <stdio.h>
#include <malloc.h>
//用二叉链表来实现一颗二叉树
//1.定义用于组成树的结点
//树：tree 二叉树：binary tree
// 二叉搜索树：binary search tree
#define MAXSIZE 10

typedef char ElementType;
typedef struct node{
    //1.数据项
    ElementType data;
    //2.地址项
    //地址项里有两个指针，分别指向左右子树
    struct node *left;
    struct node *right;
} BTnode;
//1.创建节点
/*
 * 创建一个用于组成二叉树的结点
 * 函数名：createBTnode
 * 输入：要存储的数据
 * 输出：返回结点
 * */

BTnode *createBTnode(ElementType data){
    //1.分配空间
    BTnode *node =malloc(sizeof(BTnode));
    //2.初始化参数
    node->data=data;
    node->left=NULL;
    node->right=NULL;

    return node;

};

//中序遍历
/*
 * 输入：二叉树
 * 输出：无
 * 函数名：inOrderTraversal()
 * */
void inOrderTraversal(BTnode *tree){
    if(tree){
        //1.中序遍历左子树
        inOrderTraversal(tree->left);
        //2.访问根结点
        printf(" %c", tree->data);
        //3.中序遍历右子树
        inOrderTraversal(tree->right);
    }

}

//前序
void preOrderTraversal(BTnode *tree){
    if(tree){
        //1.访问根结点
        printf(" %c", tree->data);
        //2.前序遍历左子树
        preOrderTraversal(tree->left);
        //3.前序遍历右子树
        preOrderTraversal(tree->right);
    }

}
//层序遍历
//1.要有队列  2.借助队列的进队和出队操作来实现层序遍历
/*
 * 步骤：
 * （1）创建队列
 *  （2）将树的根结点进队
 *  while(!队列为空)
 *  { 3. 将队首元素出队，打印
 *    4. 将出队结点的子结点进队列
 *  }
 *
 * */
/*
 * 函数名：levelOrder()
 * 输入：树（树的根结点）
 * 输出：在队列打印元素，没有返回值
 * */;
 /*
  * 队列：Queue
  * 函数：
  * 1.创建队列 createQueue()
  * 2.进队:Enqueue(Queue queue,ElementType data)
  * 3.出队:Delqueue(Queue queue)  返回值：队首元素
  * 4.判断是否为空:isEmpty(Queue queue)
  * 5.判断是否为满:isFull(Queue queue)
  * */
 typedef struct queue Queue;
 typedef BTnode *ElementType2;
 struct queue{
     ElementType2 data[MAXSIZE];
     int front ,rear;
 };
Queue *createQueue(){
    Queue *queue = malloc(sizeof(Queue));
    queue->front=0;
    queue->rear=0;
    return queue;
}
void Enqueue(Queue *queue,ElementType2 data){
    if((queue->rear+1)%MAXSIZE==queue->front)
        return;
    //1.先赋值
    queue->data[queue->rear]=data;
    //2.再移动
    queue->rear=(queue->rear+1)%MAXSIZE;
}
ElementType2 Delqueue(Queue *queue)  {
    if(queue->front==queue->rear)
        return NULL;
   //队不为空进行删除操作
    //1.队首元素输出
   //return queue.data[queue.front++];
   ElementType2 data=queue->data[queue->front];
   queue->front=(queue->front+1)%MAXSIZE;
   return data;

}
int isEmpty(Queue *queue){
    return queue->front==queue->rear;
}

 void levelOrder(BTnode *tree){
     //默认的大前提，树不为空
     //1.创建队列
     Queue *queue=createQueue();
     //2.将树的根结点进队
     Enqueue(queue,tree);
     //3.循环操作，直到条件不满足
     BTnode *tmp;
     while(!isEmpty(queue)){
         //3.1 出队
         tmp=Delqueue(queue);
         //3.1 并打印
         printf("%c",tmp->data);
         //3.2 子结点进队
         if(tmp->left)
             Enqueue(queue,tmp->left);
         if(tmp->right)
             Enqueue(queue,tmp->right);
     }
 }
 //根据扩展树的前序遍历去动态建立二叉树
 /*
  * 函数名：createBTauto()
  * 输入：无，所需要的数据在函数里面通过scanf()来获取
  * 输出：返回值就是创建好的二叉树，数据类型BTnode
  *
  * */
 BTnode *createBTauto(){
     //1.获取
     char str;
     scanf("%c",&str);
     //2.创建结点
     BTnode *root;
     if(str=='#'){
         root=NULL;
     } else{
         //3.分配空间
         root = malloc(sizeof (BTnode));
         root->data=str;
         root->left= createBTauto();
         root->right= createBTauto();
     }
     return root;
 }

int main() {
   /* //创建6个结点并赋值
    BTnode *nodeA = createBTnode('A');
    BTnode *nodeB = createBTnode('B');
    BTnode *nodeD = createBTnode('D');
    BTnode *nodeF = createBTnode('F');
    BTnode *nodeI = createBTnode('I');
    BTnode *nodeL = createBTnode('L');
    //按照逻辑关系链接
    nodeA->left=nodeB;//根结点
    nodeA->right=nodeD;

    nodeB->right=nodeF;//根结点的左子树
    nodeF->left=nodeL;

    nodeD->left=nodeI;//根结点的右子树
*/
    //创建9个结点并赋值
    BTnode *nodeA = createBTnode('A');
    BTnode *nodeB = createBTnode('B');
    BTnode *nodeC = createBTnode('C');
    BTnode *nodeD = createBTnode('D');
    BTnode *nodeE = createBTnode('E');
    BTnode *nodeF = createBTnode('F');
    BTnode *nodeG = createBTnode('G');
    BTnode *nodeI = createBTnode('I');
    BTnode *nodeH = createBTnode('H');

    nodeA->left=nodeB;
    nodeA->right=nodeC;


    nodeB->left=nodeD;
    nodeB->right=nodeF;
    nodeF->left=nodeE;

    nodeC->left=nodeG;
    nodeC->right=nodeI;
    nodeG->right=nodeH;


    //中序遍历
    printf("Inorder:");
    inOrderTraversal(nodeA);
    printf("\n");
     //2.前序遍历
    printf("Preorder:");
    preOrderTraversal(nodeA);
    printf("\n");

    printf("层序遍历：\n");
    levelOrder(nodeA);
    BTnode *BT = createBTauto();
    printf("打印创建好的二叉树：\n");
    printf("层序遍历：\n");
    levelOrder(BT);
    //AB#FL###DI###
    //printf("Hello, World!\n");

    return 0;
}
